# 101. 拉马车
# https://www.lanqiao.cn/problems/101/learning/?page=1&first_category_id=1&second_category_id=3&contain_answer=true
# Date: 2025/1/17
from collections import deque
from functools import reduce


def carriage(que_a: deque, que_b: deque):
    stack = []  # 表示牌桌上的牌
    turn_a = True  # 表示A或者B出牌, True表示A出牌, False表示B出牌
    while que_a and que_b:
        if turn_a:  # A的出牌轮次
            card_a = que_a.popleft()
            if card_a in stack:  # 赢走桌面上对应的牌
                idx = stack.index(card_a)
                que_a.append(card_a)
                temp = stack[idx:]
                que_a.extend(temp[::-1])
                stack = stack[:idx]
            else:
                stack.append(card_a)
                turn_a = False

        else:  # B的出牌轮次
            card_b = que_b.popleft()
            if card_b in stack:  # 赢走桌面上对应的牌
                idx = stack.index(card_b)
                que_b.append(card_b)
                temp = stack[idx:]
                que_b.extend(temp[::-1])
                stack = stack[:idx]
            else:
                stack.append(card_b)
                turn_a = True
    return que_a if que_a else que_b


if __name__ == '__main__':
    print(reduce(lambda x, y: x + y,
                 carriage(deque(str(c) for c in "K8XKA2A95A"), deque(str(c) for c in "27K5J5Q6K4"))))
    # 9K2A62KAX58K57KJ5
    print(reduce(lambda x, y: x + y,
                 carriage(deque(str(c) for c in "96J5A898QA"), deque(str(c) for c in "6278A7Q973"))))
    # 2J9A7QA6Q6889977
    print(reduce(lambda x, y: x + y,
                 carriage(deque(str(c) for c in "X6AA59X4Q48K"), deque(str(c) for c in "JQ258XK3A435"))))
    # Q24QAXA3A34K5845689XJ5
